"""Several combinatory functions on lists."""

def subsequence (l, n):
    """Returns all possible subsequences of l with n elements."""
    if n==1: return [[x] for x in l]
    assert (len (l) >= n)
    if len(l)==n: return [l]
    assert (len (l) > n)
    a = l[0]
    b = l[1:]
    return subsequence (b, n) + [[a]+x for x in subsequence (b, n-1)]
    
def permutations(l):
    """Iterates over all permutations of l."""
    if len (l) == 1: yield l
    else:
        first = l[0]
        for p in permutations(l[1:]):
            for i in range(len(p)+1):
                yield p[:i]+[first]+p[i:]
            
def allpairings (a,b):
    """Iterates over all pairings between elements of a and elements of b."""
    if len(a) < len (b): a = a + [None]*(len(b)-len(a))
    elif len(b) < len (a): b = a + [None]*(len(a)-len(b))
    for pb in permutations(b): yield zip(a,pb)

def allsamplings (ll):
    """Given a list [l0, l1, ... ln-1], where each li is a list, returns all
    possible lists which may be obtained by picking one element of each li."""
    if len(ll)==1: 
        for x in ll[0]: yield [x]
    else: 
        for x in ll[0]:
            for s in allsamplings(ll[1:]):
                yield [x]+s
    
def interleave (a,b):
    """Given two lists, returns all possible interleavings of them."""
    if a==[]: return [b]
    result = []
    if len(a)==1:
        for i in range(len(b)+1):
            result.append(b[:i]+a+b[i:])
    else:
        k = 1
        for x in interleave(a[1:],b):
            for i in range(k):
                result.append(x[:i]+[a[0]]+x[i:])
            k += 1
    return result
